#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int uniquePaths(int m, int n)
    {
//        return reach(1,1,m,n);
        vector<vector<int>> dp(m, vector<int>(n,1));
        for(int i = 1; i < m; i++)
            for(int j = 1; j < n; j++)
            {
                dp[i][j] = dp[i-1][j]+dp[i][j-1];
            }
        return dp[m-1][n-1];
    }
    int reach(int pos_x, int pos_y, int m, int n)
    {
        if(pos_x == m && pos_y == n)
            return 1;

        int count = 0;
        if(pos_x < m)
            count += reach(pos_x+1, pos_y,m,n);
        if(pos_y < n)
            count += reach(pos_x,pos_y+1,m,n);
        return count;
    }

};

int main()
{

    return 0;
}
